"""
@Project:Python crawler
@File:bubbkesort.py
@Author:邓建祥
@Date:9:47
"""
import random


# 冒泡排序
list = [5,2,3,4,6,8,1,9,7,10]
print("冒泡待排>",list)


for i in range(len(list)-1):
    for j in range(len(list)-i-1):
        if list[j] < list[j+1]:
            list[j],list[j+1] = list[j+1],list[j]

print("冒泡排序>",list)
print()


# 选择排序
a = [1,6,21,3,5]
print("选择待排>",a)
def selectSort(list):
    for i in range(len(list)-1):
        min_list = i
        for j in range(i+1, len(list)):
            if list[j] < list[min_list]:
                min_list = j
        list[min_list],list[i] = list[i],list[min_list]
        # print(list)
    return list


print("选择排序>",selectSort((a)))
print()


# 插入排序
def insertion_sort(arr):
    # 第一层for表示循环插入的遍数
    for i in range(len(arr)):
        # 当前需要插入的元素
        current = arr[i]
        # 与当前元素比较的比较元素
        pre_index = i -1
        while pre_index >= 0 and arr[pre_index] > current:
            # 当比较元素大于当前元素则把比较元素后移
            arr[pre_index + 1] = arr[pre_index]
            # 往前选择下一个比较元素
            pre_index -= 1
        # 当比较元素大于当前元素则把比较元素后裔
        arr[pre_index + 1] = current
    return arr


A = [11, 99, 88, 66, 33, 22, 44, 77, 55]
print('插入待排>', A)
B = insertion_sort(A)
print("插入排序>",B)


# 快速排序
def quickSort(alist):
    if not alist:
        return alist

    pivot = random.choice(alist)
    # print(pivot)
    equalList = []
    smallerList = []
    biggerList = []

    for item in alist:
        if item < pivot:
            smallerList.append(item)
        elif item == pivot:
            equalList.append(item)
        else:
            biggerList.append(item)
    return quickSort(biggerList)+equalList+quickSort(smallerList)


# 待排序列表
a = [3, 1 , 2, 5, 7, 4]
print()
print("快速待排>", a)
su = quickSort(a)
print("快速排序>",su)


# 希尔排序
def shell_sort(arr):
    # 取整计算增量（间隔）值
    gap = len(arr) // 2
    while gap > 0:
        # 从增量值开始遍历比较
        for i in range(gap, len(arr)):
            j = i
            current = arr[i]
            # 元素与他同列前面的元素比较，如果比前面的小则互换，其实，这就是插入排序
            while j - gap >= 0 and current < arr[j -gap]:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = current
            # 缩小增量（间隔）值
        gap //= 2
    return arr

A = [3,6,2,1,9,4,7,5,0]
print()
print("希尔待排>", A)
sorted_arr = shell_sort(A)
print("希尔排序>",sorted_arr)


# 归并排序代码
def merge_sort(lst):
    # 递归结束条件
    if len(lst) <= 1:
        return lst

    # 分析问题，并递归调用
    middle = len(lst)//2
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])

    # 合并左右半部分，完成排序
    merged_lst = []
    while left and right:
        if left[0] <= right[0]:
            merged_lst.append(left.pop(0))
        else:
            merged_lst.append(right.pop(0))

    # 如果左部分或右部分还右剩余，那就拼接到已拍好序的列表中
    merged_lst.extend(right if right else left)
    return merged_lst


A = [11, 18, 15, 14, 12, 16, 19, 13, 17,10]
B = merge_sort(A)
print()
print("归并待排>", A)
print("归并排序>", B)


# 计数排序代码
def counting_sort(array):
    largest = max(array); smallest = min(array)  # 获取最大，最小值
    counter = [0 for i in range(largest - smallest + 1)] # 用户统计个数的空数组
    idx = 0 # 桶内索引值
    for i in range(len(array)):
        counter[array[i]-smallest] += 1 # 统计每个元素出现的次数
    for j in range(len(counter)):
        while counter[j] > 0:
            array[idx] = j + smallest # 取出元素
            idx += 1
            counter[j] -= 1
    return array

print()
A = [5,2,8,9,1,2]
print("计数未排",A)
B = counting_sort(A)

print("计数排序",B)
print()

# 堆排序
from heapq import heappush,heappop


def heapsort(iterable):
    # 排好序的存入这个列表里
    h = []

    # 构建二叉堆
    for value in iterable:
        heappush(h,value)

    # 删除堆顶后，自我调整，再返回列表
    return [heappop(h) for i in range(len(h))]


lst = [8,3,5,1,9,6]
lst2 = heapsort(lst)
print("堆排序",lst2)